package com.cty._03_SolutionSeekingMindset._37_SerializeBinaryTree;

/**
 * @Auther: cty
 * @Date: 2020/7/14 9:44
 * @Description: 面试题37：序列化二叉树
 * 题目：请实现两个函数，分别用来序列化和反序列化二叉树。
 *
 * 获取返回值总结：
 * |    返回值类型      |     return-1    |    参数-n    |    全局变量-n    |
 * |基本数据类型或字符串 |        √        |      ×      |        √         |
 * |    引用类型        |        √        |      √      |        √         |
 *
 * return：应优先使用，缺点是只能获取一个返回值
 * 参数：仅适用于引用数据类型，且作为参数传递进方法的引用，不能被赋值，只能被修改
 * 全局变量：应最后使用，缺点是不符合一般编程思维
 * @version: 1.0
 */
public class SerializeBinaryTree {

    private static String currentStream = null;  // 想要两个返回值，其中一个只能用全局变量实现

    /**
     * 将二叉树序列化为字符串
     *      序列化字符串存在 serializeString中
     * @param treeRoot
     */
    public static String serialize(BinaryTreeNode treeRoot){
        if(treeRoot == null) {
            return  "$,";
        }

        String stream = treeRoot.value + ",";
        stream += serialize(treeRoot.leftChild);
        stream += serialize(treeRoot.rightChild);
        return stream;
    }  // end serialize()

    /**
     * 将字符串反序列化为二叉树
     *      反序列化二叉树根节点存在 deserializeTreeRoot
     * @param stream
     */
    public static BinaryTreeNode deserialize(String stream){
        if(stream == null)
            return null;

        currentStream = stream;
        return recDeserialize();
    }  // end deserialize()

    private static BinaryTreeNode recDeserialize(){
        String value = readNext();
        if(value == null)
            return null;

        BinaryTreeNode currentNode = new BinaryTreeNode(Integer.parseInt(value));
        currentNode.leftChild = recDeserialize();
        currentNode.rightChild = recDeserialize();
        return currentNode;
    }  // end deserialize()


    // 读取下一个","前的数据
    //      返回数字字符串
    //      返回null（当字符串为null时；当","前的数据不是数字字符串时）
    private static String readNext(){
        if(currentStream == null)
            return null;  // 字符串为null

        int index = currentStream.indexOf(",");
        if(index == -1)
            return null;  // 字符串不合法

        // 获取节点字符串
        String subString = currentStream.substring(0, index);
        for(int i=0; i<subString.length(); i++){  // 检验字符串是否合法
            int tempNum = subString.charAt(i) - '0';
            if(tempNum<0 || tempNum>9) {
                subString = null;  // 节点内容不合法
                break;
            }
        }  // end for

        // 调整当前流
        if(currentStream.length() < index+1)
            SerializeBinaryTree.currentStream = null;  // 已经到了末尾
        SerializeBinaryTree.currentStream = currentStream.substring(index+1);

        return subString;
    }  // end readNext()

}  // end class

class BinaryTreeNode{
    int value;
    BinaryTreeNode leftChild;
    BinaryTreeNode rightChild;

    public BinaryTreeNode(){};

    public BinaryTreeNode(int value){this.value = value;}
}  // end class
